//2952.需要添加的硬市的最小数量
//https://leetcode.cn/problems/minimum-number-of-coins-to-be-added/
class Solution {
    //总体思路
    //枚举区间 num=1表示右闭区间 从[0,1]开始
    //依次加上数组中的数 如果数组中的数大于num 则加上该数后 区间肯定断了 此时需要在断了的区间中添加一个数
    //这个数一般是当前区间的右闭区间的两倍2 此时可以组成 [0，2x-1]
    //依次枚举 如果加上后区间断了 就加当前右避区间的两倍
    //但是必须得排序，从小到大枚举 否则会枚举已存在的数
public:
    int minimumAddedCoins(vector<int>& coins, int target) {
        sort(coins.begin(),coins.end());
        int n = coins.size();
        int ret = 0;
        int i = 0;
        int num = 1; //一开始组成 [0,1]
        //如果num大于target 则表示已经可以组成target了
        //while中不能写i<n 因为如果数字相同或只有一个数 则target可能是一个很大的数
        //此时需要快速扩大该区间的二倍 否则循环直接跳出了
        while(num <= target)
        {
            //例如当前下标为0 指向示例1中的数
            //表示可以组成[0,1] 此时区间+1 变成 [0,1] [1,2] 合并为 [0,2] 此时num表示[0,2]可以组成
            //所以 如果该数小于当前区间的最右区间 则加上后一定会合并而不会断
            if(i<n && coins[i]<=num) num += coins[i++];
            //否则例如下标1 指向4 当区间为 [0,2]时 +4 变成 [0,2] [4,6] 区间断了 则需要添加当前[0,2]区间中
            //再+2 即[0,2] [2,4] 此时表示可以组成 [0,4]
            //再+4时 [0,4] [4,8] 可以组成 [0,8]
            //添加一个数后 ++ret
            else 
            {
                num*=2; //或 num+=num
                ++ret;
            }
        }
        return ret;
    }
};